package com.whitedust.top20;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author A
 * @since 2025/11/3 12:55
 */

public class Top15 {
    //递归回溯的基础题，全排列，剪枝即传入i点来进行剪枝
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        HashSet<Integer> hash = new HashSet<>();
        permute2(nums, path, res, hash);
        return res;
    }

    private void permute2(int[] nums, List<Integer> path, List<List<Integer>> res, HashSet<Integer> hash) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int num : nums) {
            if (!hash.contains(num)) {
                path.add(num);
                hash.add(num);
                permute2(nums, path, res, hash);
                path.remove(path.size() - 1);
                hash.remove(num);
            }
        }
    }
}
